/*
 * 10.6
 * Given a two dimensional graph with points on it, find a line which passes the most
 * number of points.
 */
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return (b==0) ? a : gcd(b, a%b);
}

typedef struct _point_t {
    int x, y;
    /* required in std::find */
    bool operator==(const struct _point_t &other) const { /* XXX: note const */
        return !memcmp(this, &other, sizeof(struct _point_t));
    }
} point_t;

typedef struct _line_t {
    int km, kn;
    int bm, bn;
    /* required in std::find */
    bool operator==(const struct _line_t &other) const { /* XXX: note const */
        return !memcmp(this, &other, sizeof(struct _line_t));
    }
} line_t;

typedef struct _compare_line_t {
    /* required in std::map/multimap */
    bool operator()(const line_t &a, const line_t &b) const { /* XXX: note const */
        if (a.kn == 0 || b.kn == 0) {
            if (a.kn != 0) {
                return true;
            }
            if (b.kn != 0) {
                return false;
            }
            return a.km < b.km;
        }
        if (a.bm == b.bm && a.bn == b.bn) {
            /* XXX: note double!!! */
            return ((double)a.km / a.kn) < ((double)b.km / b.kn);
        }
        /* XXX: note double!!! */
        return ((double)a.bm / a.bn) < ((double)b.bm / b.bn);
    }
} compare_line_t;

void search(int (*arr)[2], int n, line_t &lout, vector<point_t> &pout)
{
    multimap<line_t, point_t, compare_line_t> m;
    typedef multimap<line_t, point_t, compare_line_t>::const_iterator line_iterator;
    for (int i = 0; i < n; i++) {
        point_t pi = { arr[i][0], arr[i][1] };
        for (int j = i + 1; j < n; j++) {
            point_t pj = { arr[j][0], arr[j][1] };
            int dy = pj.y - pi.y;
            int dx = pj.x - pi.x;
            line_t l;
            if (dx == 0) {
                l.km = pj.x;
                l.kn = 0;
                l.bm = 0;
                l.bn = 0;
            } else {
                int g = gcd(dy, dx);
                l.km = dy/g;
                l.kn = dx/g;
                // y = kx + b --> b = y - kx
                int ym = l.kn * pj.y - l.km * pj.x;
                int yn = l.kn;
                g = gcd(ym, yn);
                l.bm = ym / g;
                l.bn = yn / g;
            }
            pair<line_iterator, line_iterator> pr = m.equal_range(l);
            pair<const line_t, point_t> ti = make_pair(l, pi); /* XXX: note const */
            pair<const line_t, point_t> tj = make_pair(l, pj); /* XXX: note const */
            if (std::find(pr.first, pr.second, ti) == pr.second) {
                m.insert(ti);
            }
            if (std::find(pr.first, pr.second, tj) == pr.second) {
                m.insert(tj);
            }
        }
    }
    // find max
    int max = 0;
    line_iterator maxit, maxit2;
    for (line_iterator it = m.begin(); it != m.end(); ) {
        line_iterator it2 = m.upper_bound(it->first);
        int count = m.count(it->first);
        if (max < count) {
            max = count;
            maxit = it;
            maxit2 = it2;
        }
        printf("line: k=%d/%d, b=%d/%d, count=%d\n", it->first.km, it->first.kn, it->first.bm, it->first.bn, count);
        it = it2;
    }
    lout = maxit->first;
    for (line_iterator it = maxit; it != maxit2; ++it) {
        pout.push_back(it->second);
    }
}

int main()
{
    printf("=== test1 ===\n");
    int arr[][2] = {
        { 1, 2 },
        { 3, 4 },
        { 5, 10 },
        { 6, 13 }
    };
    int size = sizeof(arr)/sizeof(arr[0]);
    line_t lout;
    vector<point_t> pout;
    search(arr, size, lout, pout);
    printf("max line: k=%d/%d, b=%d/%d\n", lout.km, lout.kn, lout.bm, lout.bn);
    printf("max points:");
    for (vector<point_t>::const_iterator it = pout.begin(); it != pout.end(); ++it) {
        printf(" [%d,%d]", it->x, it->y);
    }
    printf("\n");
    printf("=== test2 ===\n");
    int arr2[][2] = {
        { 1, 2 },
        { 3, 4 },
        { 3, 2 },
        { 3, 3 },
        { 5, 10 },
        { 6, 13 },
        { 6, 22 },
    };
    size = sizeof(arr2)/sizeof(arr2[0]);
    pout.clear();
    search(arr2, size, lout, pout);
    printf("max line: k=%d/%d, b=%d/%d\n", lout.km, lout.kn, lout.bm, lout.bn);
    printf("max points:");
    for (vector<point_t>::const_iterator it = pout.begin(); it != pout.end(); ++it) {
        printf(" [%d,%d]", it->x, it->y);
    }
    printf("\n");
    return 0;
}
